package com.PAT.UnSatisfying;

import java.util.Arrays;
import java.util.Scanner;

/**
 * Created with IntelliJ IDEA.
 *
 * @Author: zjz
 * @Date: 2022/02/16/17:11
 * @Description:
 * @Target: 差3
 */
public class 插入与归并 {

    /*
    *
    * 根据维基百科的定义：

        插入排序是迭代算法，逐一获得输入数据，逐步产生有序的输出序列。每步迭代中，算法从输入序列中取出一元素，将之插入有序序列中正确的位置。如此迭代直到全部元素有序。

        归并排序进行如下迭代操作：首先将原始序列看成 N 个只包含 1 个元素的有序子序列，然后每次迭代归并两个相邻的有序子序列，直到最后只剩下 1 个有序的序列。

        现给定原始序列和由某排序算法产生的中间序列，请你判断该算法究竟是哪种排序算法？

        输入格式：
        输入在第一行给出正整数 N (≤100)；随后一行给出原始序列的 N 个整数；最后一行给出由某排序算法产生的中间序列。
        这里假设排序的目标序列是升序。数字间以空格分隔。

        输出格式：
        首先在第 1 行中输出Insertion Sort表示插入排序、或Merge Sort表示归并排序；然后在第 2 行中输出用该排序算法再迭代一轮的结果序列。
        * 题目保证每组测试的结果是唯一的。数字间以空格分隔，且行首尾不得有多余空格。
        *
        *
        *
        *
        * 输入样例 1：
        10
        3 1 2 8 7 5 9 4 6 0
        1 2 3 7 8 5 9 4 6 0
        输出样例 1：
        Insertion Sort
        1 2 3 5 7 8 9 4 6 0
        输入样例 2：
        10
        3 1 2 8 7 5 9 4 0 6
        1 3 2 8 5 7 4 9 0 6
        输出样例 2：
        Merge Sort
        1 2 3 8 4 5 7 9 0 6
    *
    * */


    // 比对字符串可以快速得出是哪种类型
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int len = in.nextInt();
        int[] ints1 = new int[len];  // 未排序的
        int[] ints11 = new int[len];  // 未排序的
        int[] ints2 = new int[len];  // 排序中途的

        for (int i = 0; i < len; i++) {
            ints1[i] = in.nextInt();
            ints11[i] = ints1[i];
        }

        for (int i = 0; i < len; i++) {
            ints2[i] = in.nextInt();
        }
        String change = change(ints2);

        InsertSort(ints1,change);
        MergeSort(ints11,change);


    }



    // 编写下插入
    static void InsertSort(int[] ints,String ss){
        boolean flag = false;
        for (int i = 1; i < ints.length; i++) {
            for (int j = i; j > 0 && ints[j]<ints[j-1]; j--) {
                swap(ints,j,j-1);
//                System.out.println(change(ints));
            }

            if (change(ints).equals(ss)){
                System.out.println("Insertion Sort");
                flag = true;
            }else if (flag == true){
                System.out.println(change(ints));
                flag = false;
            }
        }

    }



    // 编写下归并
    static void MergeSort(int[] ints,String ss){
        boolean flag =false;
        for (int i = 2; i < ints.length; i*=2) {
            for (int j = 1; j < ints.length; j+=i) {
                if (j+i-1>ints.length){
                    Arrays.sort(ints,j-1,ints.length);
                }else {
                    Arrays.sort(ints,j-1,j+i-1);
                }
            }

            if (change(ints).equals(ss)){
                System.out.println("Merge Sort");
                flag = true;
            }else if (flag == true){
                System.out.println(change(ints));
                flag = false;
            }
        }

        Arrays.sort(ints);
        if (flag == true){
            System.out.println(change(ints));
            flag = false;
        }
    }


    // 交换器
    static void swap(int[] ints,int a,int b){
        int temp = ints[a];
        ints[a] = ints[b];
        ints[b] = temp;
    }


    // 将数组变为字符串输出
    static String change(int[] ints){
        String ss = "";
        for (int anInt : ints) {
            ss+=anInt;
            ss+=" ";
        }
        return ss.substring(0,ss.length()-1);
    }

}
